//69. x 的平方根

//暴力解法：
//int mySqrt(int x)
//{
//    long long i = 0;
//    for (i = 0; i <= x; i++)
//    {
//        if (i * i > x)
//        {
//            i = i - 1;
//            break;
//        }
//        else if (i * i == x)
//        {
//            break;
//        }
//    }
//    return i;
//}

//二分查找法：
int mySqrt(int x){
	if (1 == x)
		return 1;
	
	long long left = 1, right = x / 2;
	while (left <= right)
	{
		long long mid = left + (right - left) / 2;
		if (mid * mid < x)
			left = mid + 1;
		else if (mid * mid > x)
			right = mid - 1;
		else//相等直接返回
			return mid;
	}

	return left - 1;//最后一次left会更新到开平方+1
}